<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        var solveNQueens = function (n) {
            // 验证是否有效果 同列 同行 斜线 是否出现相同的元素
            function isValid(row, col, chessBoard, n) {
                // 同列 col相同 row递增, row < n
                // 为什么这里的i从0开始，我们要从当前列的0往下面开始数
                for (let i = 0; i < row; i++) {
                    if (chessBoard[i][col] === 'Q') {
                        return false
                    }
                }

                // 135 col - 1， row - 1 ， col >= 0 row >= 0
                // 为什么这里的i和j从row和col开始，我们从当前的位置开始，往上去查找。下面的135°同理
                for (let i = row, j = col; i >= 0 && j >= 0; i--, j--) {
                    if (chessBoard[i][j] === 'Q') {
                        return false
                    }
                }

                //45° col + 1, row - 1, col < n, row >= 0
                for (let i = row, j = col; i >= 0 && j < n; i--, j++) {
                    if (chessBoard[i][j] === 'Q') {
                        return false
                    }
                }
                return true
            }

            // 假设4个皇后 -> 二维数组好了 -> 转化为字符串形式的
            function transformChessBoard(chessBoard) {
                let chessBoardBack = []
                for (let i = 0; i < chessBoard.length; i++) {
                    /* 
                        [
                            ['.','.'],
                            [],
                            [],
                            []
                        ]
                    */
                    let chessStr = ''
                    for (let j = 0; j < chessBoard[i].length; j++) {
                        chessStr += chessBoard[i][j]
                    }
                    chessBoardBack.push(chessStr)
                }
                return chessBoardBack
            }

            // 递归函数 
            function backtracing(row, chessBoard) {
                // 退出条件
                if (row === n) {
                    // 在这里 把数组放大result里面去 而不是在 transformChessBoard 方法里面
                    result.push(transformChessBoard(chessBoard))
                    return
                }

                // for循环
                for (let col = 0; col < n; col++) {
                    // 每一次for循环 只会针对一行
                    if (isValid(row, col, chessBoard, n)) {
                        debugger
                        chessBoard[row][col] = 'Q'
                        // row + 1 表示进入了下一行
                        backtracing(row + 1, chessBoard)
                        // 这里代表了回溯
                        chessBoard[row][col] = '.'
                    }
                }
            }

            // 判断是否n已经是4了，如果是的话，就放到result里面去返回result
            let result = []
            let chessBoard = new Array(n).fill([]).map(() => new Array(n).fill('.'))
            backtracing(0, chessBoard)
            return result
        };
        console.log(solveNQueens(4));
    </script>
</body>

</html>